package shortestPath;

public class BellmanFord {
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();

		//Create the distance array. 		
		int[][] distanceArray = new int[matrix.length][matrix.length];
		
		//Initialise the distance array.
		for(int i=0; i<matrix.length; i++){
			for(int j=0; j<matrix.length; j++){
				distanceArray[i][j] = Integer.MAX_VALUE/3;
			}
		}
		distanceArray[0][0] = matrix[0][0];
		
		//
		for(int k=0; k<matrix.length*matrix.length; k++){
			for(int i=0; i<matrix.length; i++){
				for(int j=0; j<matrix.length; j++){
					//&& conditions check to see if [i][j] is at the edge of the matrix.
					if(i!=0 && distanceArray[i-1][j] + matrix[i][j] < distanceArray[i][j]){
						distanceArray[i][j] = distanceArray[i-1][j] + matrix[i][j];
					}
					if(i!=matrix.length-1 && distanceArray[i+1][j] + matrix[i][j] < distanceArray[i][j]){
						distanceArray[i][j] = distanceArray[i+1][j] + matrix[i][j];
					}
					if(j!=0 && distanceArray[i][j-1] + matrix[i][j] < distanceArray[i][j]){
						distanceArray[i][j] = distanceArray[i][j-1] + matrix[i][j];
					}
					if(j!=matrix.length-1 && distanceArray[i][j+1] + matrix[i][j] < distanceArray[i][j]){
						distanceArray[i][j] = distanceArray[i][j+1] + matrix[i][j];
					}
				}
			}
		}
		
		if(showAnswer) System.out.println(distanceArray[matrix.length-1][matrix.length-1]);
		return (System.currentTimeMillis()-startTime);
	}
}
